package com.study.webapp.leetcode;

public class ShortestPath {

    public static void main(String[] args) {
        int [][]arr= {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println("路径：");
        System.out.println("最小值为："+minPath(arr));
    }

    private static int minPath(int[][] arr) {
        if(arr==null||arr.length==0) {
            return 0;
        }
        int row=arr.length;
        int col=arr[0].length;
        //用来保存计算的中间值
        int [][]cache=new int[row][col];
        cache[0][0]=arr[0][0];
        for(int i=1;i<col;i++) {
            cache[0][i]=cache[0][i-1]+arr[0][i];
        }
        for(int j=1;j<row;j++) {
            cache[j][0]=cache[j-1][0]+arr[j][0];
        }
        //在遍历二维数组的过程中不断把计算结果保存到cache中
        for(int i=1;i<row;i++) {
            for(int j=1;j<col;j++) {
                //可以确定选择的路线为a[i][j-1]
                if(cache[i-1][j]>cache[i][j-1]) {
                    cache[i][j]=cache[i][j-1]+arr[i][j];
                    System.out.println("["+i+","+(j-1)+"] ");
                    //可以确定选择的路线为arr[i-1][j]
                }else {
                    cache[i][j]=cache[i-1][j]+arr[i][j];
                    System.out.println("["+(i-1)+","+j+"] ");
                }
            }
        }
        System.out.println("["+(row-1)+","+(col-1)+"]");
        return cache[row-1][col-1];
    }
}
